{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "fa1f99f1",
   "metadata": {},
   "source": [
    "# 指导思想\n",
    "简单来说，聚类完成的数学问题可以简化描述如下：\n",
    "样本集 $$D = \\{\\vec x_1,\\vec x_2,\\vec x_3, \\cdots, \\vec x_m\\}$$ 包含$\\mathbf{m}$个无标记样本，<br>每个样本$$\\vec x_i=(x_{i1}, x_{i2},x_{i3},\\cdots, x_{in})$$是一个$\\mathbf{n}$维特征向量,<br>聚类算法是将样本集$D$划分为$k$个不相交的子集$$\\{C_l|l=1,2,\\cdots,k\\}$$<br>同时满足\n",
    "$$\n",
    "\\left\\{\n",
    "\\begin{array}{ll}\n",
    "C_{l^\\prime}\\bigcap_{l^{\\prime}\\ne l}C_l = \\emptyset \\\\\n",
    "D = \\bigcup^{k}_{l=1}C_l\n",
    "\\end{array}\n",
    "\\right.\n",
    "$$\n",
    "相应的，我们使用$$\\lambda_j \\in \\{1,2,\\cdots, k\\}$$表示样本$\\vec x_j$的簇标记 <br>\n",
    "那么，聚类的结果可以用包含$m$个元素的簇标记向量$$\\vec\\lambda=(\\lambda_1,\\lambda_2,\\cdots,\\lambda_m)$$表示\n",
    "\n",
    "简单来说，聚类算法应当包含以下两个考量因素\n",
    "1. 性能度量\n",
    "2. 距离计算"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "282ce0b3",
   "metadata": {},
   "source": [
    "## 性能度量\n",
    "1. 主要目标是使聚类结果的簇内相似度(intra-cluster similarity)高且簇间相似度(inter-cluster similarity)低\n",
    "2. 大致分为两类\n",
    "    1. 将聚类结果与某个参考模型相比较，称为外部指标\n",
    "    2. 直接考察聚类记过而不利用任何参考模型，称为内部指标"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a549b28a",
   "metadata": {},
   "source": [
    "## 距离计算\n",
    "1. 距离计算公式需要具备以下四个性质<br>\n",
    "    1. 非负性 - 距离非负 <br>\n",
    "    2. 同一性 - 存在0值 <br>\n",
    "    3. 对称性 - 交换顺序距离相同 <br>\n",
    "    4. 直递性 - 三角不等式  <br>\n",
    "2. 对于属性，我们也能分为连续属性和离散属性\n",
    "3. 对于连续属性，我们常用闵可夫斯基距离进行度量\n",
    "$$\n",
    "    dist(\\mathbf{x_i},\\mathbf{x_j}) = {(\\sum^{n}_{u=1}{\\lvert x_{iu}-x_{ju}\\rvert}^{p})}^{1/p}\n",
    "$$\n",
    "当$p=1$时，退化为曼哈顿距离<br>\n",
    "当$p=2$时，退化为欧式距离<br>\n",
    "4. 对于离散属性，如果离散属性能够被参数化，并且参数化值能够有序，那么可以转化为连续属性进行计算\n",
    "5. 对于离散属性，如果不能够参数化，可以VDM方法进行距离计算"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "903cd761",
   "metadata": {},
   "source": [
    "# 聚类思想分类及常用算法"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "918a2496",
   "metadata": {},
   "source": [
    "## 原型聚类\n",
    "此类算法假设聚类结构能够通过一组原型刻画<br>\n",
    "算法先对原型进行初始化，然后对原型进行迭代更新求解<br>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "96cd66f8",
   "metadata": {},
   "source": [
    "### k-means\n",
    "1. 随机选取k个点作为核\n",
    "2. 遍历点集，将每个点按照最近距离划入核所在聚类中\n",
    "3. 更新聚类的核\n",
    "4. 重复2.3直到核不再更新，或者核更新值小于设定值"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "87ac844b",
   "metadata": {},
   "source": [
    "### LVQ - Learning Vector Quantization\n",
    "1. 确定k个原型向量，同时给每一个向量预先分配一个标签，标签的类别数量可以不同于原型向量数量，这两个都是超参数\n",
    "2. 遍历点集，寻找每个点最近的原型向量，比较二者的标签\n",
    "3. 如果标记相同，那么更新原型向量向该点靠拢，学习速率也是一个超参数\n",
    "4. 如果标记不同，那么更新原型向量向该点远离，学习速率也是一个超参数\n",
    "5. 重复2.3.4直到原型向量不再更新或更新值小于设定值"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4c287d6b",
   "metadata": {},
   "source": [
    "### 高斯混合聚类\n",
    "1. 我们假设每一个聚类都是一个多元高斯分布，那么总体高斯混合分布就是每一个聚类高斯分布的加权平均\n",
    "$$\n",
    "    p_{M}(x) = \\sum^{k}_{i=1}\\alpha_i p(\\mathbf{x}|\\mathbf{\\mu_i},\\,\\mathbf{\\Sigma_i})\n",
    "$$\n",
    "2. 首先初始化每个聚类的$\\alpha, \\mu, \\Sigma$\n",
    "3. 通过初始化的值计算后验概率，将数据点重新划入不同的聚类，然后更新每个聚类的$\\alpha, \\mu, \\Sigma$\n",
    "4. 重复3直到满足条件"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dbf25d53",
   "metadata": {},
   "source": [
    "## 密度聚类\n",
    "此类算法假设聚类结构能够通过样本分布的紧密程度确定<br>\n",
    "密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99be91b3",
   "metadata": {},
   "source": [
    "### DBSCAN\n",
    "1. 通过两个超参数$(\\epsilon,MinPts)$遍历数据集找到所有的核心点\n",
    "2. 以任意核心点为出发点，寻找其密度可达的样本生成聚类簇，密度可达表示该点与簇内所有点的距离小于$\\epsilon$\n",
    "3. 从未访问点中去除已入簇点，重复2，直到所有点被访问"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c15cb9eb",
   "metadata": {},
   "source": [
    "### OPTICS\n",
    "Ordering Points To Identify the Cluster Structure"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c8004ec4",
   "metadata": {},
   "source": [
    "## 层次聚类\n",
    "层次聚类试图在不同层次对数据集进行划分，从而形成树形的聚类结构"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3958173",
   "metadata": {},
   "source": [
    "### AGNES\n",
    "采用自底向上的聚和方式<br>\n",
    "1. 首先将每一个样本看成一个聚类簇\n",
    "2. 计算每个聚类簇之间的平均距离，然后合并距离近的两个聚类\n",
    "3. 重复2直到达到目标要求的聚类簇数量"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d12e2935",
   "metadata": {},
   "source": [
    "### BIRCH"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8d487d33",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.7"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "277.797px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
